#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

struct Node{
    int x;
    int y;
    Node* parent;
    bool wall;
    bool searched; 
    Node(int xx=0,int yy=0,Node* p=NULL,bool w=false,bool s=false):x(xx),y(yy),parent(p),wall(w),searched(s){
        cout<<"("<<x<<","<<y<<"):"<<wall<<endl;
    };
};

int main(){
    /*
    0 0 1 0 1 //0表示可走，1表示墙
    0 1 1 1 0 //只能↑↓←→走，不能斜着走
    0 0 0 0 0 
    0 1 1 1 0
    0 0 0 1 0
    */
    vector<vector<int>> info{{0,0,1,0,1},{0,1,1,1,0},{0,0,0,0,0},{0,1,1,1,0},{0,0,0,1,0}};
    int x_len=info.size();
    int y_len=info[0].size();
    //Node tmp;
    vector<vector<Node>> migong; 
    for(int i=0;i<x_len;i++){
        vector<Node> tmp;
        for(int j=0;j<y_len;j++){
            Node node{i,j,NULL,info[i][j],false};
            //cout<<info[i][j]<<" ";
            tmp.push_back(node);
        }
        //cout<<endl;
        migong.push_back(tmp);
    }

    for(int i=0;i<x_len;i++){
        for(int j=0;j<y_len;j++){
            cout<<migong[i][j].wall<<" ";
        }
        cout<<endl;
    }
    stack<Node*> dfs;
    migong[0][0].searched=true;
    dfs.push(&migong[0][0]);
    Node* cur;
    Node* next;
    bool down=true;
    while (!dfs.empty()){   
        cur=dfs.top();
        //dfs.pop();
        down=true;

        //上
        if(cur->x>0){
            next=&migong[cur->x-1][cur->y];
            if((next->wall==0)&&(!(next->searched))){
                cout<<"cur:("<<cur->x<<","<<cur->y<<"),up:("<<next->x<<","<<next->y<<")"<<endl;
                next->searched=true;
                next->parent=cur;
                dfs.push(next);
                down=false;
                if((next->x==x_len-1)&&(next->y==y_len-1)){
                    break;
                }
            }
        }

        //下
        if(cur->x<x_len-1){
            next=&migong[cur->x+1][cur->y];
            if((next->wall==0)&&(!(next->searched))){
                cout<<"cur:("<<cur->x<<","<<cur->y<<"),down:("<<next->x<<","<<next->y<<")"<<endl;
                next->searched=true;
                next->parent=cur;
                dfs.push(next);
                down=false;
                if((next->x==x_len-1)&&(next->y==y_len-1)){
                    break;
                }
            }
        }

        //左
        if(cur->y>0){
            next=&migong[cur->x][cur->y-1];
            if((next->wall==0)&&(!(next->searched))){
                cout<<"cur:("<<cur->x<<","<<cur->y<<"),left:("<<next->x<<","<<next->y<<")"<<endl;
                next->searched=true;
                next->parent=cur;
                dfs.push(next);
                down=false;
                if((next->x==x_len-1)&&(next->y==y_len-1)){
                    break;
                }
            }
        }

        //右
        if(cur->y<y_len-1){
            next=&migong[cur->x][cur->y+1];
            if((next->wall==0)&&(!(next->searched))){
                cout<<"cur:("<<cur->x<<","<<cur->y<<"),right:("<<next->x<<","<<next->y<<")"<<endl;
                next->searched=true;
                next->parent=cur;
                dfs.push(next);
                down=false;
                if((next->x==x_len-1)&&(next->y==y_len-1)){
                    break;
                }
            }
        }

        if(down){
            dfs.pop();
        } 
    }

    //跳出循环
    vector<Node*> res;
    res.push_back(next);
    //cout<<"("<<next->x<<","<<next->y<<")"<<endl;
    while (next->parent!=NULL){
        next=next->parent;
        //cout<<"("<<next->x<<","<<next->y<<")"<<endl;
        res.push_back(next);
    }

    for(int i=res.size()-1;i>0;i--){
        cout<<"("<<res[i]->x<<","<<res[i]->y<<")"<<endl;
    } 
    return 0;
}
